package com.datastructures2.graph.无向图;

/**
 * 是否为二分图(双色问题)
 * @author MaoLin Wang
 * @date 2020/2/2117:50
 */
public class TwoColor {
    private boolean[] marked;
    private boolean[] color;
    private boolean isTwoColorable=true;
    public TwoColor(Graph graph){
        marked=new boolean[graph.V()];
        color=new  boolean[graph.V()];
        for (int i = 0; i < graph.V(); i++) {
            if (!marked[i]){
                dfs(graph,i);
            }
        }
    }

    private void dfs(Graph graph, int v) {
        marked[v]=true;
        for (int w: graph.adj(v)){
            if (!marked[w]){
                color[w]=!color[v];
                dfs(graph,w);
            }else if (color[w]==color[v]){
                isTwoColorable=false;
                break;
            }
        }
    }

    public boolean isBipartite(){
        return isTwoColorable;
    }
}
